1. Field of the Invention
The present invention is generally directed to encoding, and more particularly to implementations of Reed-Solomon encoding.
2. Background
Errors can occur in the transmission or storage of data. Reed-Solomon (RS) encoding is a well-known error correction encoding scheme that can be used to correct such errors. An RS encoder computes redundant bits, called parity bytes, from the data that is to be transmitted or stored. The parity bytes are then concatenated with the data bytes. The concatenation of the parity bytes and the data bytes is referred to as a codeword. The redundant parity bits included in the codeword can be used by an RS decoder to correct for errors that occur during transmission or storage.
A popular RS code provides a codeword containing 255 bytes, with 8-bit symbols. Of the 255 bytes in the codeword, 223 bytes are data bytes and 32 bytes are parity bytes. Using such an RS code, an RS decoder can correct errors in up to 16 bytes per codeword. In general, for a codeword including K data bytes and R parity bytes, an RS decoder can correct errors in up to R/2 bytes per codeword.
The parity bytes of a codeword are computed by performing various calculations based on mathematical operations in a Galois field. A Galois field is a “finite field,” or more generally a “field,” as studied in the branch of mathematics known as abstract algebra. Conceptually, the Galois field computation scheme can be understood by representing the data symbols of the codeword as coefficients of a polynomial. Using the properties of polynomial multiplication and division, the parity bytes can be computed from both the polynomial representing the data bytes and a primitive polynomial of the Galois field.
While this computation scheme can result in an effective error correction code, the computation of the RS parity bytes is relatively complex. As a result of this complexity, an RS encoder may require complex circuitry, and therefore may be prohibitively costly to manufacture. In addition, the RS encoding scheme may require complex algorithms to implement, and therefore may be too slow for current applications.
Given the foregoing, what is needed is a system and method for performing optimized RS encoding in a microprocessor. Such a system and method should be able to compute a fixed number of RS parity bytes that are commonly used in RS codes and a programmable number of RS parity bytes.